package 数组;

/**
 * @Project: data-structure-and-algorithms
 * @Package: 数组
 * @ClassName: t1004_1
 * @Author: zhouyihe
 * @Date: 2025/11/26 14:07
 * @Description: 最大连续1的个数III--二分查找法
 */
public class t1004_1 {
    /**
     * 找到数组中最大连续1的个数（允许翻转最多k个0）
     * 使用前缀和+二分查找的方法实现滑动窗口
     *
     * @param nums 输入的二进制数组，只包含0和1
     * @param k    允许翻转的0的最大个数
     * @return 最长连续1的长度（包含翻转后的1）
     */
    public int longestOnes(int[] nums, int k) {
        int n = nums.length;
        // 构建前缀和数组，p[i]表示前i个元素中0的个数
        int[] p = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            p[i] = p[i - 1] + (1 - nums[i - 1]);
        }

        int ans = 0;
        // 遍历右端点，通过二分查找找到满足条件的最左端点
        for (int right = 0; right < n; right++) {
            int left = binarySearch(p, p[right + 1] - k);
            ans = Math.max(ans, right - left + 1);
        }
        return ans;
    }

    public int binarySearch(int[] p, int target) {
        int low = 0, high = p.length - 1;
        while (low < high) {
            int mid = (high - low) / 2 + low;
            if (p[mid] < target) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        return low;
    }
}
